SS 18, 2

a)

b)

c)

d)

e)

f)

WS 18, 1

a) ER-Model zu relationalem Model

b)

i)

ii) IST-Beziehung

iii)

c)

i) Schlüsselkandidat

Ein Schlüssel Kandidat der Relation R ist eine Attributmenge, wo

ii) Primärschlüssel

Ein spezieller/konkret ausgewählter Schlüsselkandidat

iii) Kein Fremdschlüssel im ER-Model

Fremdschlüssel sind bereits implizit über Beziehungen modelliert

WS 18, 4

a)

i) (Un-)vollständige Historie

da wir nicht alle Operationen aus T1 bzw. T2 in P1 haben, kann es sich beim hinzufügen/weglassen von {a} oder {b} nicht um eine vollständige Historie handeln.

ii) (Nicht/) vollständige Historie

Ergänzung um mindestens drei Kanten.

Nicht vollständige Historie

Bei hinzunahme von {b,d,c} haben keine vollständige Historie, da durch den entstehneden Zyklus wir nicht mehr die partielle Ordnung haben

Vollständige Historie

Bei hinzunahme von {a,b,d} haben wir eine vollständige Historie

iii)

Anmerkung zu {a,c,e}

Hier ist nochmal visuell gezeigt, wieso wir keine vollständige Historie haben (das 3. Kriterium ist verletzt).

b)

i)
(1)H1=r1[B]r2[B]w2[B]c2
Dirty Read
(2)H~1=r1[B]w1[B]r2[B]w2[B]c2a1
Lost-Update
(3)H^1=r1[B]r2[B]w2[B]c2c1
Non-Repeatable Read
(4)H˙1=r1[B]r2[B]w2[B]r2[B]c2
ii) ACID-Eigenschaften

Acid steht für:

Vermutung: Verletzte Eigenschaften
iii) Minimale Rücksetzbarkeitsklasse
1) Dirty Read

Wir nehmen eine generelle From von "dirty read" und zeigen, dass RC nicht möglich ist:

(5)wi[x]<rj[x]<ai<cj

Für diese Sequenz halten wir fest:

2) Lost Update

Die foglende Sequenz ist ein generelle From von "Lost Update" und möglich in RC, ACA:

(6)wi[x]<wj[x]<ci

Wir können aber nicht STRICT haben, denn Lost updates fordert wi[x]<wj[x]<ci, aber STRICT verlangt ci<wj[x].

WS 19, 2

a)

 

b)

i)
(7)halt idkeyvalue0hat U-Bahnhofja
ii)

Es sollen alle in Properties enthalten Informationen ausgegeben werden von Einträgen die zwar eine halt_id haben, aber keine (aktive) Haltestelle.

iii)

Es werden nun alle Properties ausgegeben, falls es mindestens eine Haltestelle gibt mit halt_id in Properties.

c)

d)

e)

f)

Select * from prop where halt_id not in (select distinct id from halt)

WS 19, 3

a)

Relation R(A, B, C, D, E, F) und funktionale Abhängigkeiten.

Gegeben sei die Relation R(A, B, C, D, E, F) mit den folgenden funktionalen Abhängigkeiten:

(8)F={ACDA,CA,CE,CDF,FB}
i) Schlüsselkandidat DC

Schlüsselkandidaten sind Attributmengen, für welche

Behauptung

Es handelt sich bei {DC} um einen Schlüsselkandidat, da

{C}+={A,C,E}{D}+={D}
Beweis
(9){CDCD,CA}=>CDA(A,P)
F+{CA (),CDA(A, P),CDCD (R),CDD (P),CDC (P),CE (),CDE (A,P),CDF (),CDF()FB()CDB (A,P)}
ii) Höchste Normalformen

1.-Normalform ist gegeben, da alle Attribute atomar vorliegen.

Die 1.-NF ist die höchste Normalform, da eine partielle Abhängigkeit gibt:

b)

Relation R(A, B, C, D) und funktionale Abhängigkeiten.

Gegeben sei die Relation R(A, B, C, D) . Alle Attribute sind atomar. R mit den funktionalen Abhängigkeiten F ist in 2NF.

(10)F={AC, BDA}
i) Erweiterung zu F2 für 1.-Normalform
(11)F2={AC,BDA,BA}

1. Normalform liegt vor, da alle Attribute atomar sind

2. Normalform ist nicht gegeben, da es eine partielle Abhängigkeit gibt

ii) Erweiterung zu F2 für 3.-Normalform
(12)F3={AC,BDA,ABD}

1. Normalform ist gegeben, da alle Attribute atomar sind

2. Normalform ist gegeben, da es keine partiellen Abhängigkeiten gibt

3. Normalform ist gegeben, da es keine transitive Abhängigkeit zwischen einem Schlüssel und Nicht-Primattributen

c)

 

d)
(13)ΠSName(sea)(14)(15)ΠSName(σDepth>Depth2(sea×ρSName2, Depth2(sea)))
i) Informationen der Anfrage

Der/Die See/Seen mit der geringsten Tiefe. 1. wird abgezogen von 2.:

  1. Die Namen aller Seen

  2. Die Namen aller Seen außer den See mit der geringsten Tiefe

ii) Anfragebaum und B*-Baum-Index

WS 19, 4

a) Vollständige Historie

P1

Wir benötigen die Katen a,c,d um eine vollständige Historie zu erhalten.

P2

Bei P2 ist bereits eine vollständige Historie gegeben, ohne dass eine Kante ergänzt werden muss.

P3

Damit P3 eine vollständige Historie ist, ergänzen wir die Kanten {a,e}.

b) Locking

i) schwaches/starkes/kein 2-Phasen Sperrprotokoll
(16)S1:rl1[x] w1[x] r1[x] ul1[x] c1(17)S2:wl2[x] w2[x] wl2[y] ul2[x] w2[y] ul2[y] c2(18)S3:wl3[x] w3[x] wl3[y] r3[x] ul3[x] ul3[y] c3(19)S4:wl4[x] w4[x] w4[y] wl4[y] ul4[x] wl4[z] ul4[z] ul4[y] c4
S1

S1 ist kein (Zwei-Phasen) Sperrprotokoll, da ein ein write w1[x] existiert, ohne vorherigen write-lock wl1[x].

S2

S2 ist schwaches Zwei-Phasen Sperrprotokoll, da zwar ein 2PL vorliegt, aber ul2[x]<wl2[y] vorliegt.

S3

S3 ist kein (Zwei-Phasen) Sperrprotokoll, da ein write erfolgt ohne vorherigen write-lock bei w3[y].

S4

S4 ist kein Zwei-Phasen Sperrprotokoll, da es eine lock-Operation nach einer unlock-Operation gibt mit ul4[x]<wl4[z].

ii) Striktes 2PL
(20)S5:rl5[x] r5[x] rl6[x] r6[x] wl6[y] w6[y] ul6[x] ul6[y] c6 wl5[x] w5[x] ul5[x] c5

c) Serialisierbarkeit

i) Definition von konfligierenden Operationen

Zwei Operationen p, q von unterschiedlichen Transaktionen konfligieren:

ii) Serialisierbarkeitsgraph
(21)H1=w1[x]c1w2[x]r2[x]w3[x]c2(22)H2=w2[x]r1[x]w4[x]r3[x]c3c2w1[x]c1a4(23)H3=r3[x]r2[y]w1[y]w3[y]r3[y]w1[x]c1c2c3
SG(H1)

SG(H2)

SG(H3)

WS 20, 1

a) ER-Modell zu relationales Modell: Teilnehmerkardinalität

b) EER-Modelierungstechnik

c) Pros/Cons für Vermschelzen

+ ausgeben des Attributs der Entität geht schneller

+ weniger Relationen

- eventuel. viele Nullwerte die grundlos Speicher vebrauchen (falls Fremdschlüssel mit NULL-Wert zugelassen sind)

WS 20, 2

a)

b)

c)

d)

e)

 

WS 20, 3

a)
(24)ΠA(rs)=ΠA(r)ΠA(s)
Beweis
b) Synthesealgorithmus
(25)F2:={ACDA,CAE,CDEF,FB}

Das Ergebnis des Synthesealgorithmus ist somit

(26)Z={(CDAEF,{CD}),(CAE,{C}),(FB,{F})}
c)

Gegeben sei die Relation S(A, B, C, D, E) mit den folgenden funktionalen Abhängigkeiten:

(27)F2:={ABCD,DBC,BE}

Die Attribute seien alle atomar. Betrachten Sie als mögliche Normalformen 1NF, 2NF, 3NF und BCNF.

i) Schlüsselkandidaten von S
ii) Höchste Normalform von S

Was ist die höchste Normalform, die S erfüllt? Begründen Sie.

iii) Zerlegungen von S
(28)F2:={ABCD,DBC,BE}

Gegeben seien die folgenden Zerlegungen von S (mit F2 ), wobei die Schlüssel nicht explizit angegeben sind:

Z1={S1(A,D),S2(D,B,C),S3(B,E)}Z2={S4(A,B,C,D),S5(B,E)}

Explizite Angabe der funktionalen Abhängigkeiten:

(29)FS1={AD},FS2={DBC},FS3={BE}(30)FS4={ABCD,DBC},FS5={BE}
Die höchste Normalform von FS1,FS2 und FS3 ist BCNF

Wir sehen in FS1,FS2 und FS3, dass für jedes FD die linke Seite der Schlüssel ist

Die höchste Normalform von FS4 ist 3.-Normalform

Damit lässt sich nun die 3.-Normalform bestimmen:

Die höchste Normalform von FS5 ist BCNF
Z1: Nicht Abhängigkeitstreu, Verbundtreu

das "Andere Kriterium" lässt sich nicht anwenden, da abhängigkeitstreue nicht gegeben ist

Z2: Abhängigkeitstreu, Verbundtreu

WS 20, 4

a)

i) Transaktion

Transaktion ist partielle Ordnung mit Ordnungsrelation <, so dass gilt:

  1. Ti{ri[x],wi[x]x ist ein Datenobjekt}{ai,ci},

  2. aiTiciTi,

  3. Wenn es sich bei t um ci oder ai handelt, dann gilt für jede andere Operation pTi: p<t und

  4. Wenn ri[x],wi[x]Ti, dann ri[x]<iwi[x] oder wi[x]<iri[x].

ii) Konfliktäquivalenz und Rücksetzbarkeitsklassen

Aus Konfliktäquivalenz folgt nicht, dass die Rücksetzbarkeitsklassen übereinstimmen.

Um RC und ACA zu bestimmen, wird von gewissen Operationen nach dem zeitliche Zusammenhang zu einem "commit" oder "abort" gefragt. Bei Konfliktäquivalenz geht es lediglich um die Übereinstimmung von konfligierender Operationen, folglich wird keine Aussage über die Rücksetzbarkeitsklassen gemacht.

Beispiel

H1 und H2 besitzen sind Konfliktäquivaalent, aber die Rücksetzbarkeitsklassen stimmen nicht überein:

(31)H1=r1[X] w1[X] c1 r2[X] c2ACA(32)H2=r1[X] w1[X] r2[X] c1 c2RC aber nicht ACA

iii) Rücksetzbarkeitsklassen

  1. Alle committed Inhalte Konsistent sind

  2. Kaskadierendes Rücksetzen verhindert wird

  3. Verhindern von Dirty Reads, Unrepeatable Reads, Lost Updates

b)

Gegeben sind die folgenden partiellen Historien:

(33)H1=r1[A] w1[A] r1[B] w1[B] c1(34)H2=r1[A] r1[B] w2[A] r2[B] w1[A] c1 c2(35)H3=w3[A] r1[A] r2[A] r3[B] w2[B] w1[B] c1 c2 c3(36)H4=w1[A] r1[C] r2[B] w2[A] w3[B] r3[C] w1[C] c1 c2 c3

i) Serialisierbarkeitsgraph

SG(H1)

SG(H2)

SG(H3)

SG(H4)

ii) Rücksetzbarkeitsklassen

(37)HistorieRCACASTRICTnicht rücksetzbarH1XXXH2XXH3X
H1

 

H2

H3

 

SS 21, 4

a) STRICT

b) Transaktionen oder nicht

A

Es handelt sich nicht um eine Transaktion, da entweder c ODER a vorkommen darf.

B

Es handelt sich um eine Transaktion, da alle Kriterien erfüllt sind.

C

Es handelt sich nicht um eine Transaktion, da a<w[y] Bedingung 3. verletzt.

D

Es handelt sich um eine Transaktion, da alle Kriterien erfüllt sind.

c)

(38)H1=r1[A] r2[B] w2[A] w3[C] w1[B] r1[C] r2[C] c1 c2 c3(39)H2=w1[B] r2[A] w2[B] r1[A] w3[A] r3[A] c2 c3(40)H3=r1[A] r2[B] r3[C] r1[C] r2[A] r3[B] c1 c2 c3
H1

H1 ist nicht serialisierbar, da der Serialisierbarkeitsgraph einen Zyklus enthält.

H2

H2 ist serialisierbar, da der Serialisierbarkeitsgraph keinen Zyklus enthält.

H3

H3 ist serialisierbar, da der Serialisierbarkeitsgraph keinen Zyklus enthält.

d)

Gegeben seien die folgenden Transaktionen T1 und T2

(41)T1: r1[A] r1[B] w1[A] r1[C] w1[D] c1(42)T2: r2[A] r2[C] w2[A] c2

sowie die Schedules

(43)H4: r1[A] r2[A] r1[B] r2[C] w2[A] w1[A] r1[C] w1[D] c1 c2(44)H5: r1[A] r1[B] w1[A] r2[C] w2[A] r1[C] w1[D] c1 c2(45)H6: r2[A] r2[C] r1[A] r1[B] w1[A] w2[A] r1[C] w1[D] c2 c1
i) Lost Update

ii) Striktes 2PL: Transaktion
T1:rl1[A]r1[A]rl1[B]r[B]wl1[A]w1[A]rl1[C]r1[C]wl[D]w1[D]ul1[A]ul1[B]ul1[C]c1T2:rl2[A]r2[A]rl2C]r2[C]wl2[A]w2[A]ul2[A]ul2[C]c2
iii) Striktes 2PL: Histories
H4 ist nicht ausführbar

H4 kann nicht ausgeführt werden, da es ein read-lock auf A gibt (rl1[A]) und damit die Anfrage des write-locks auf A bei wl2[A]) abgelehnt wird.

H5 ist nicht ausführbar

H5 kann nicht ausgeführt werden, da wir ein read-lock auf A haben (rl1[A]) und damit die write-lock Anfrage auf A bei wl2[A] abgelehnt wird.

H6 ist nicht ausführbar

H6 kann nicht ausgeführt werden, da wir ein read-lock auf A haben (r2[A]) und damit die die write-lock Anfrage auf A bei wl1[A] abgelehnt wird.

iv) Nicht Striktem 2PL
(46)rl1[A]r1[A]rl1[B]r1[B]wl1[A]w1[A]rl1[C]ul1[A]rl2[A]r2[A]rl2[C](47)r2[C]wl2[A]w2[A]r1[C]wl1[D]w1[D]yl1[C]ul1[D]ul1[B]c1ul2[A]ul2[C]c2